#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


from operator import mul, add, sub


def dot_product(v1, v2):
    '''
    dot_product/inner_product 只支持两个向量, 输出一个标量scalar.
    对应numpy.dot
    '''
    assert len(v1) == len(v2), (v1, v2)
    product_vector = map(mul, v1, v2)
    return sum(product_vector)

def multiply_1(m1, m2):
    '''normal method
        从结果element角度.
    '''
    row = len(m1)
    col = len(m2[0])
    one_row = [0] * col
    result = [list(one_row) for r in range(row)]

    for r in range(row):
        for c in range(col):
            # row =
            the_col = [ i[c] for i in m2]
            result[r][c] = dot_product(m1[r], the_col)

    return result

def matrix_power(mat, nth):
    ''' return mat^nth '''
    if nth == 0:
        return identity(len(mat))
    if nth == 1:
        return mat

    remain = nth % 2
    half = nth // 2

    half_power = matrix_power(mat, half)
    even_power = multiply_1(half_power, half_power)

    if remain:
        return multiply_1(even_power, mat)
    else:
        return even_power

class MarkovTrans:
    def __init__(self, row, column):
        self.row = row
        self.col = column

        self.transfer_size = row * column

        self.make_transfer()

    def make_transfer(self):
        one_row = [0] * self.transfer_size
        self.transfer_matrix = [ list(one_row) for i in range(self.transfer_size)]

        for src_grid in range(self.transfer_size):
            neighbors = self.neighbors_num(src_grid)
            prob = 1 / neighbors

            print("neighbors cnt ", neighbors, "of ", src_grid)
            print("prob  ", prob)

            for dest_grid in self.neighbors_kth(src_grid):
                print("dest grid", dest_grid)
                self.transfer_matrix[src_grid][dest_grid] = prob
            print()

    def ntimes(self, n):
        return matrix_power(self.transfer_matrix, n)

    def valid_row(self, row_th):
        return  0 <= row_th < self.row

    def valid_col(self, col_th):
        return  0 <= col_th < self.col

    def valid_pos(self, row_th, col_th):
        return self.valid_row(row_th) and self.valid_col(col_th)

    def neighbors_num(self, kth):
        row = kth // self.row
        col = kth % self.row

        # print(row, col, "of ", kth)

        if row != self.row - 1 or col != self.col - 1:
            cnt = 0
            if self.valid_row(row - 1): cnt += 1
            if self.valid_row(row + 1): cnt += 1
            if self.valid_col(col - 1): cnt += 1
            if self.valid_col(col + 1): cnt += 1
            # print("cnt ", cnt)
            return cnt

        else:
            return 1

    def neighbors_kth(self, kth):
        row = kth // self.row
        col =  kth % self.row

        if row == self.row-1 and col == self.col-1:
            yield kth
        else:
            for col_offset in [-1, 1]:
                new_col = col + col_offset
                if self.valid_col(new_col):
                    print('new :', row, ' ', new_col)
                    yield row * self.row + new_col      # kth 从0开始

            for row_offset in [-1, 1]:
                new_row = row + row_offset
                if self.valid_row(new_row):
                    print('new :', new_row, ' ', col)
                    yield new_row * self.row + col      # kth 从0开始


def main():
    print("start main")

    markov = MarkovTrans(2, 2)
    # markov = MarkovTrans(3, 3)
    print(markov.transfer_matrix)

    print( markov.ntimes(3) )
    print( markov.ntimes(4) )
    print( markov.ntimes(5) )
    print( markov.ntimes(10) )
    print( markov.ntimes(50) )
    print( markov.ntimes(100) )
    # print(markov.transfer_matrix)

if __name__ == "__main__":
    main()
